package com.hjx.leetcode;


/**
 * 5. 最长回文子串
 *
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * 示例 1：
 *
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 *
 * 输入: "cbbd"
 * 输出: "bb"
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode_5 {

    public String longestPalindrome1(String s) {
        char[] chars = s.toCharArray();

        String palindrome = "";
        for (int i = 0; i < chars.length; i++){
            int targetLen = 2 * i + 1;
            String sss = s.substring(0, targetLen);
            boolean flag = true;
            for (int j = 0; j <= targetLen / 2; j++){
                flag = flag && sss.charAt(j) == sss.charAt(targetLen - 1 - j);
                if (!flag){
                    break;
                }
            }
            if (flag){
                if (targetLen >= palindrome.length()){
                    palindrome = sss;
                }
            }

        }


        return palindrome;
    }

    public String longestPalindrome(String s) {

        char[] chars = s.toCharArray();

        String palindrome = "";
        for (int i = 0; i < chars.length ; i++){
            for (int j = i; j < chars.length; j++){

                String target = s.substring(i, j + 1);
                if(isTarget(target) && target.length() >= palindrome.length()){
                    palindrome = target;
                }

            }
        }
        return palindrome;
    }

    private boolean isTarget(String target) {
        for (int k = 0; k < target.length() / 2 ; k++){
            if (target.charAt(k) != target.charAt(target.length() - 1 - k)){
                return false;
            }
        }
        return true;
    }
}
